
/*-------------------------------------------------------------------------
 *
 * pairingheap.c
 *	  A Pairing Heap implementation
 *
 * 配对堆是一种数据结构，适用于实现优先队列。它易于实现，提供摊销O(1)
 * 的插入和查找最小操作，以及摊销O(log n)的删除最小操作。
 *
 * 配对堆在以下论文中首次被描述：
 *
 *	Michael L. Fredman, Robert Sedgewick, Daniel D. Sleator, and Robert E.
 *	 Tarjan. 1986.
 *	The pairing heap: a new form of self-adjusting heap.
 *	Algorithmica 1, 1 (January 1986), pages 111-129. DOI: 10.1007/BF01840439
 *
 * Portions Copyright (c) 2012-2022, PostgreSQL Global Development Group
 *
 * IDENTIFICATION
 *	  src/backend/lib/pairingheap.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "lib/pairingheap.h"

static pairingheap_node *fc_merge(pairingheap *fc_heap, pairingheap_node *fc_a,
							   pairingheap_node *fc_b);
static pairingheap_node *fc_merge_children(pairingheap *fc_heap,
										pairingheap_node *fc_children);

/*
 * pairingheap_allocate
 *
 * 返回一个指向新分配堆的指针，堆的属性由给定的比较函数定义，
 * 该函数将使用 'arg' 指定的附加参数调用。
 */
pairingheap *
pairingheap_allocate(pairingheap_comparator fc_compare, void *fc_arg)
{
	pairingheap *fc_heap;

	fc_heap = (pairingheap *) palloc(sizeof(pairingheap));
	fc_heap->ph_compare = fc_compare;
	fc_heap->ph_arg = fc_arg;

	fc_heap->ph_root = NULL;

	return fc_heap;
}

/*
 * pairingheap_free
 *
 * 释放给定 pairingheap 占用的内存。
 *
 * 注意：堆中的节点不会被释放！
 */
void pairingheap_free(pairingheap *fc_heap)
{
	pfree(fc_heap);
}

/*
 * 一个帮助函数，用于将两个子堆合并为一个。
 *
 * 值较小的子堆被作为另一个子堆的子节点（假设为最大堆）。
 *
 * 输入节点的 next_sibling 和 prev_or_parent 指针被忽略。
 * 返回时，返回节点的 next_sibling 和 prev_or_parent 指针是垃圾。
 */
static pairingheap_node *
fc_merge(pairingheap *fc_heap, pairingheap_node *fc_a, pairingheap_node *fc_b)
{
	if (fc_a == NULL)
		return fc_b;
	if (fc_b == NULL)
		return fc_a;

	/* 交换 'a' 和 'b'，使 'a' 是值较大的那个 */
	if (fc_heap->ph_compare(fc_a, fc_b, fc_heap->ph_arg) < 0)
	{
		pairingheap_node *fc_tmp;

		fc_tmp = fc_a;
		fc_a = fc_b;
		fc_b = fc_tmp;
	}

	/* 并将 'b' 作为 'a' 的子节点 */
	if (fc_a->first_child)
		fc_a->first_child->prev_or_parent = fc_b;
	fc_b->prev_or_parent = fc_a;
	fc_b->next_sibling = fc_a->first_child;
	fc_a->first_child = fc_b;

	return fc_a;
}

/*
 * pairingheap_add
 *
 * 以 O(1) 的时间将给定节点添加到堆中。
 */
void pairingheap_add(pairingheap *fc_heap, pairingheap_node *fc_node)
{
	fc_node->first_child = NULL;

	/* 将新节点链接为新树 */
	fc_heap->ph_root = fc_merge(fc_heap, fc_heap->ph_root, fc_node);
	fc_heap->ph_root->prev_or_parent = NULL;
	fc_heap->ph_root->next_sibling = NULL;
}

/*
 * pairingheap_first
 *
 * 返回指向堆中第一个（根，最上面）节点的指针，而不修改堆。
 * 调用者必须确保此例程不用于空堆。始终为 O(1)。
 */
pairingheap_node *
pairingheap_first(pairingheap *fc_heap)
{
	Assert(!pairingheap_is_empty(fc_heap));

	return fc_heap->ph_root;
}

/*
 * pairingheap_remove_first
 *
 * 移除堆中的第一个（根，最上面）节点，并在重新平衡堆后返回指向该节点的指针。
 * 调用者必须确保此例程不用于空堆。O(log n) 平均。
 */
pairingheap_node *
pairingheap_remove_first(pairingheap *fc_heap)
{
	pairingheap_node *fc_result;
	pairingheap_node *fc_children;

	Assert(!pairingheap_is_empty(fc_heap));

	/* 移除根节点，并形成其子节点的新堆。 */
	fc_result = fc_heap->ph_root;
	fc_children = fc_result->first_child;

	fc_heap->ph_root = fc_merge_children(fc_heap, fc_children);
	if (fc_heap->ph_root)
	{
		fc_heap->ph_root->prev_or_parent = NULL;
		fc_heap->ph_root->next_sibling = NULL;
	}

	return fc_result;
}

/*
 * 从堆中移除 'node'。O(log n) 平均。
 */
void pairingheap_remove(pairingheap *fc_heap, pairingheap_node *fc_node)
{
	pairingheap_node *fc_children;
	pairingheap_node *fc_replacement;
	pairingheap_node *fc_next_sibling;
	pairingheap_node **fc_prev_ptr;

	/*
	 * 如果被移除的节点恰好是根节点，使用
	 * pairingheap_remove_first() 进行操作。
	 */
	if (fc_node == fc_heap->ph_root)
	{
		(void) pairingheap_remove_first(fc_heap);
		return;
	}

	/*
	 * 在修改任何内容之前，记住被移除节点的 first_child 和
	 * next_sibling 指针。
	 */
	fc_children = fc_node->first_child;
	fc_next_sibling = fc_node->next_sibling;

	/*
	 * 还要找到被移除节点在其前一个兄弟中的指针，或者
	 * 如果这是其父节点的第一个子节点，则在其父节点中。
	 */
	if (fc_node->prev_or_parent->first_child == fc_node)
		fc_prev_ptr = &fc_node->prev_or_parent->first_child;
	else
		fc_prev_ptr = &fc_node->prev_or_parent->next_sibling;
	Assert(*fc_prev_ptr == fc_node);

	/*
	 * 如果该节点有子节点，生成一个新的子堆并将
	 * 子堆链接到被移除节点的位置。否则只需解除链接此
	 * 节点。
	 */
	if (fc_children)
	{
		fc_replacement = fc_merge_children(fc_heap, fc_children);

		fc_replacement->prev_or_parent = fc_node->prev_or_parent;
		fc_replacement->next_sibling = fc_node->next_sibling;
		*fc_prev_ptr = fc_replacement;
		if (fc_next_sibling)
			fc_next_sibling->prev_or_parent = fc_replacement;
	}
	else
	{
		*fc_prev_ptr = fc_next_sibling;
		if (fc_next_sibling)
			fc_next_sibling->prev_or_parent = fc_node->prev_or_parent;
	}
}

/*
 * 将子堆列表合并为一个单一的堆。
 *
 * 这实现了基本的两次合并策略，首先从左到右形成对，
 * 然后合并这些对。
 */
static pairingheap_node *
fc_merge_children(pairingheap *fc_heap, pairingheap_node *fc_children)
{
	pairingheap_node *fc_curr,
			   *fc_next;
	pairingheap_node *fc_pairs;
	pairingheap_node *fc_newroot;

	if (fc_children == NULL || fc_children->next_sibling == NULL)
		return fc_children;

	/* 从左到右遍历子堆，成对合并 */
	fc_next = fc_children;
	fc_pairs = NULL;
	for (;;)
	{
		fc_curr = fc_next;

		if (fc_curr == NULL)
			break;

		if (fc_curr->next_sibling == NULL)
		{
			/* 列表末尾的最后一个奇数节点 */
			fc_curr->next_sibling = fc_pairs;
			fc_pairs = fc_curr;
			break;
		}

		fc_next = fc_curr->next_sibling->next_sibling;

		/* 合并此和下一个子堆，并添加到 'pairs' 列表中。 */

		fc_curr = fc_merge(fc_heap, fc_curr, fc_curr->next_sibling);
		fc_curr->next_sibling = fc_pairs;
		fc_pairs = fc_curr;
	}

	/*
	 * 将所有对合并在一起以形成一个单一的堆。
	 */
	fc_newroot = fc_pairs;
	fc_next = fc_pairs->next_sibling;
	while (fc_next)
	{
		fc_curr = fc_next;
		fc_next = fc_curr->next_sibling;

		fc_newroot = fc_merge(fc_heap, fc_newroot, fc_curr);
	}

	return fc_newroot;
}

/*
 * 一个调试函数，用于将堆的内容以字符串形式输出。
 *
 * 'dumpfunc' 回调将单个节点的字符串表示附加到 StringInfo。
 * 'opaque' 可用于向回调传递更多信息。
 */
#ifdef PAIRINGHEAP_DEBUG
static void fc_pairingheap_dump_recurse(StringInfo fc_buf,
						 pairingheap_node *fc_node,
						 void (*fc_dumpfunc) (pairingheap_node *node, StringInfo buf, void *opaque),
						 void *fc_opaque,
						 int fc_depth,
						 pairingheap_node *fc_prev_or_parent)
{
	while (fc_node)
	{
		Assert(fc_node->prev_or_parent == fc_prev_or_parent);

		appendStringInfoSpaces(fc_buf, fc_depth * 4);
		fc_dumpfunc(fc_node, fc_buf, fc_opaque);
		appendStringInfoChar(fc_buf, '\n');
		if (fc_node->first_child)
			fc_pairingheap_dump_recurse(fc_buf, fc_node->first_child, fc_dumpfunc, fc_opaque, fc_depth + 1, fc_node);
		fc_prev_or_parent = fc_node;
		fc_node = fc_node->next_sibling;
	}
}

char * pairingheap_dump(pairingheap *fc_heap,
				 void (*fc_dumpfunc) (pairingheap_node *node, StringInfo buf, void *opaque),
				 void *fc_opaque)
{
	StringInfoData fc_buf;

	if (!fc_heap->ph_root)
		return pstrdup("(empty)");

	initStringInfo(&fc_buf);

	fc_pairingheap_dump_recurse(&fc_buf, fc_heap->ph_root, fc_dumpfunc, fc_opaque, 0, NULL);

	return fc_buf.data;
}
#endif
